import java.util.ArrayList;
import java.util.List;

class Solution14 {
    // 创建全局变量
    // 先一一映射
    String[] hash = new String[] { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
    List<String> ret;
    StringBuffer path;

    public List<String> letterCombinations(String digits) {
        ret = new ArrayList<>();
        path = new StringBuffer();
        // 边界条件判断
        if (digits.length() == 0) {
            return ret;
        }
        dfs(digits, 0);
        return ret;
    }

    public void dfs(String digits, int pos) {
        // 递归结束条件
        if (pos == digits.length()) {
            ret.add(path.toString());
            return;
        }
        // 字符转换为数字
        String s = hash[digits.charAt(pos) - '0'];
        // 遍历这个字符串
        for (int i = 0; i < s.length(); i++) {
            // 取出来一个字符
            char c = s.charAt(i);
            // 进行添加
            path.append(c);
            dfs(digits, pos + 1);
            // 回溯 -- > 恢复现场
            path.deleteCharAt(path.length() - 1);
        }
    }

}